package cn.edu.scut.hsrc.synonymity;

/**
 * 前缀树类
 * 
 * @file PrefixTrie.java
 * @author feiyu
 * 
 */
public class PrefixTrie {
	private Node root;

	/**
	 * 
	 * 构造函数
	 */
	public PrefixTrie() {
		root = new BranchNode(' ');
	}

	/**
	 * 插入字符串，如果字符串本身已经存在，插入失败，就返回false；如果不存在，就执行插入操作，返回true
	 * @param word
	 * @return
	 */
	public boolean insert(String word) {
		word += "$";
		char[] chars = word.toCharArray();
		Node currentNode = root;
		char c;
		for (int i = 0; i < chars.length; i++) {
			c = chars[i];
			if (c == '$') {
				if(currentNode.contains(c))
					return false;
				Node leaf = new LeafNode();
				currentNode.addChild('$', leaf);
			} else {
				if (currentNode.contains(c)) {
					currentNode = currentNode.next(c);
				} else {
					Node branch = new BranchNode(c);
					currentNode.addChild(c, branch);
					currentNode = branch;
				}
			}
		}
		return true;
	}

	/**
	 * 删除字符串
	 * @param word
	 * @return 存在就删除，
	 */
	public boolean delete(String word) {
		word += "$";
		char[] chars = word.toCharArray();
		Node formerBranchNode = root;
		char formerc = chars[0];
		Node currentNode = root;
		char c;
		int i=0;
		for (; i < chars.length; i++) {
			c = chars[i];
			Node next = currentNode.next(c);
			if(next != null)
			{
				if(currentNode.sizeOfChildren() != 1)
				{
					formerBranchNode = currentNode;
					formerc = c;
				}
				currentNode = next;
			}else {
				return false;
			}
		}
		formerBranchNode.removeChild(formerc);
		return true;
			
	}

	/**
	 * 搜索字符串
	 * @param word
	 * @return 找到了返回true，没有找到返回false
	 */
	public boolean search(String word) {
		word += "$";
		char[] chars = word.toCharArray();
		Node currentNode = root;
		char c;
		for (int i = 0; i < chars.length; i++) {
			c = chars[i];
			if (c == '$' && currentNode.contains(c)) {
				return true;
			} else {
				if (currentNode.contains(c)) {
					currentNode = currentNode.next(c);
				} else {
					return false;
				}
			}
		}
		return false;
	}
	
	public static void main(String[] args) {
		PrefixTrie trie = new PrefixTrie();
		trie.insert("中国");
		trie.insert("中华人民");
		trie.insert("");
		System.out.println(trie.search(""));  
        System.out.println(trie.search("中华人民共和国"));  
        System.out.println(trie.delete("中国"));  
        System.out.println(trie.delete(""));
        System.out.println(trie.search(""));
        System.out.println(trie.search("中国人"));  
        System.out.println(trie.search("中"));  
        System.out.println(trie.search("中国"));
        System.out.println(trie.search("中华人民"));
	}
}